Ich schreibe gerade einen grundlegenden Parser für eine XML-Variante. Als Übung implementiere ich einen tabellengesteuerten LL-Parser. Dies ist mein Beispiel für die BNF-Grammatik: % Token Name Datenzeichenfolge %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: name attr close_tag close_tag: ">" elem_or_data "" | "/>" ;; elem_or_data: "<" open_tag elem_or_data | Daten elem_or_data | / * epsilon * / ;; attr: name ":" string attr | / * epsilon * / ;; Ist diese Grammatik korrekt? Jedes Terminalliteral steht zwischen Anführungszeichen. Die abstrakten Terminals werden durch% token angegeben. Ich codiere einen handgeschriebenen Lexer, um meine Eingabe in eine Token-Liste umzuwandeln. Wie würde ich die abstrakten Terminals tokenisieren?
2021-03-03 08:11:10
Der klassische Ansatz wäre, für jedes mögliche Terminal einen regulären Ausdruck (oder einen anderen Erkenner) zu schreiben.
Was Sie "abstrakte" Terminals nennen, die vollkommen konkret sind, sind tatsächlich Terminals, deren zugehörige Muster mehr als eine mögliche Eingabezeichenfolge erkennen. Die tatsächlich erkannte Zeichenfolge (oder eine berechnete Funktion dieser Zeichenfolge) sollte als semantischer Wert des Tokens an den Parser übergeben werden.
Nominell führt der Tokeniser an jedem Punkt in der Eingabezeichenfolge alle Erkenner aus und wählt den mit der längsten Übereinstimmung aus. (Dies ist die sogenannte "Maximum Munch" -Regel.) Dies kann normalerweise optimiert werden, insbesondere wenn alle Muster reguläre Ausdrücke sind. (F) lex übernimmt diese Optimierung beispielsweise für Sie.
Eine Komplikation in Ihrem Fall ist, dass die Tokenisierung Ihrer Sprache kontextabhängig ist. Insbesondere wenn das Ziel elem_or_data ist, sind die einzigen möglichen Token <,